163. Missing Ranges
Easy

You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are in the inclusive range.

A number x is considered missing if x is in the range [lower, upper] and x is not in nums.

Return the smallest sorted list of ranges that cover every missing number exactly. That is, no element of nums is in any of the ranges, and each missing number is in one of the ranges.

Each range [a,b] in the list should be output as:

  • "a->b" if a != b
  • "a" if a == b

 

Example 1:

Input: nums = [0,1,3,50,75], lower = 0, upper = 99
Output: ["2","4->49","51->74","76->99"]
Explanation: The ranges are:
[2,2] --> "2"
[4,49] --> "4->49"
[51,74] --> "51->74"
[76,99] --> "76->99"

Example 2:

Input: nums = [], lower = 1, upper = 1
Output: ["1"]
Explanation: The only missing range is [1,1], which becomes "1".

Example 3:

Input: nums = [], lower = -3, upper = -1
Output: ["-3->-1"]
Explanation: The only missing range is [-3,-1], which becomes "-3->-1".

Example 4:

Input: nums = [-1], lower = -1, upper = -1
Output: []
Explanation: There are no missing ranges since there are no missing numbers.

Example 5:

Input: nums = [-1], lower = -2, upper = -1
Output: ["-2"]

 

Constraints:

  • -109 <= lower <= upper <= 109
  • 0 <= nums.length <= 100
  • lower <= nums[i] <= upper
  • All the values of nums are unique.
Accepted
125,228
Submissions
444,882
Seen this question in a real interview before?
Companies
Related Topics
Similar Questions

Average Rating: 4.81 (36 votes)

Premium

Video Solution


 

Solution Article


Approach 1: Linear Scan

Intuition and Algorithm

Since the input array, nums, is sorted ascendingly and all the elements in it are within the given [lower, upper] bounds, we can simply check consecutive elements to see if they differ by one or not. If they don't, then we have found a missing range.

  • When nums[i] - nums[i-1] == 1, we know that there are no missing elements between nums[i-1] and nums[i].
  • When nums[i] - nums[i-1] > 1, we know that the range of elements, [nums[i-1] + 1, nums[i] - 1], is missing.

missing ranges

However, there are two edge cases:

  • Edge case 1: If we don't start with lower as the first element of the array, we will need to include [lower, num[0] - 1] as a missing range as well.

missing ranges

  • Edge case 2: Similarly, if we don't end with upper as the last element of the array, we will need to include [nums[n-1] + 1, upper] as a missing range as well. Note n here is the length of the input array, nums.

Complexity Analysis

Let NN be the length of the input array.

  • Time complexity : O(N)O(N).

    This is because we are only iterating over the array once, and at each step, we're performing O(1)O(1) operations. We treat the string building as O(1)O(1) because the strings can never be more than a fixed size.

  • Space complexity : O(1)O(1).

    The output list has a worst case size of O(N)O(N). This case occurs when we have a missing range between each of the consecutive elements in the input array (for example, if the input array contains all even numbers between lower and upper). We aren't using any other additional space, beyond fixed-sized constants that don't grow with the size of the input.

    However, output space that is simply used to return the output (and not to do any processing) is not counted for the purpose of space complexity analysis. For this reason, the overall space complexity is O(1)O(1).

Report Article Issue

Comments: 25
ArizonaZervas's avatar
Read More

Am I the only one to think that the explanation is brilliant? (visuals helps a lot) The code is also very readable, if I was an interviewer I would like to see code like this where its broken down into helper functions and the edge cases clearly called out.

33
Show 2 replies
Reply
Share
Report
dattanimihir1865's avatar
Read More

I did not find this easy :(

24
Show 3 replies
Reply
Share
Report
danwuSBU's avatar
Read More

Python, no extra memory, just traversing nums:

class Solution:
    def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]:
        result = []

        def add(low, high):
            if low > high:
                return
            if low == high:
                result.append(str(low))
            else:
                result.append(str(low) + '->' + str(high))

        if not nums: # edge case
            add(lower, upper)
            return result

        add(lower, nums[0] - 1)

        for x in range(len(nums)):
            add(nums[x - 1] + 1, nums[x] - 1)

        add(nums[-1] + 1, upper)

        return result

6
Reply
Share
Report
user5557I's avatar
Read More

This one was asked to me.

3
Show 2 replies
Reply
Share
Report
jcodem's avatar
Read More

That video walkthrough was very well done. Thank you.

3
Reply
Share
Report
wareag1e's avatar
Read More

Although the problem is boring, I have to admit that the provided solution is really elegant.
Thanks for the implementation so that I find my coding ability is not even close at all. :(

3
Show 1 reply
Reply
Share
Report
aldominium's avatar
Read More

I definetly would not categorize this as an easy problem :(

4
Reply
Share
Report
RogerFederer's avatar
Read More

Python solution with list concatenation, easier to understand.

class Solution(object):

    def findMissingRanges(self, nums, lower, upper):
        res = []
        nums = [lower-1] + nums + [upper+1]
        for i in range(1, len(nums)):
            curr, prev = nums[i], nums[i-1]
            if curr - prev > 1:
                self.addRange(res, prev, curr)
        return res

    def addRange(self, res, low, high):
        if low + 2 == high:
            res.append(str(low+1))
        else:
            res.append(str(low+1) + '->' + str(high-1))

4
Reply
Share
Report
seritake's avatar
Read More

My simple solution using zip()

class Solution:
    def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]:
        ans = []
        for n1, n2 in zip([lower-1, *nums], [*nums, upper+1]):
            if n2 - n1 == 2:
                ans.append(str(n1 + 1))
            elif n2 - n1 > 2:
                ans.append(str(n1+1) + "->" + str(n2 - 1))
        return ans
            

1
Reply
Share
Report
onesuccess's avatar
Read More

My solution in C++

vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
    vector<string> res;
    int l = lower, r = upper, n = nums.size();
    for (int i = 0; i <= n; i ++) {
        if (i) l = nums[i - 1] + 1;
        r = i == n ? upper: nums[i] - 1;
        if (r == l - 1) continue;
        if (r == l) {
            res.push_back(to_string(l));
        } else {
            res.push_back(to_string(l) + "->" + to_string(r));
        }
    }
    return res;
}

1
Show 1 reply
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
05/25/2021 09:05Accepted0 ms7 MBcpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
This list is empty.